package com.itheima.algorithm.dynamicprogramming;

import java.util.Arrays;
import java.util.Comparator;

/**
 * <h3>无重叠区间</h3>
 */
public class EraseOverlapIntervalsLeetcode435 {
    public static void main(String[] args) {

        String input = "[[1,2],[2,3],[3,4],[1,3]]";
        int[][] intervals = Arrays.stream(input.substring(1, input.length() - 1).split("(?<=]),(?=\\[)"))
                .map(s -> Arrays.stream(s.substring(1, s.length() - 1).split(","))
                        .mapToInt(Integer::parseInt)
                        .toArray())
                .toArray(int[][]::new);

        System.out.println(eraseOverlapIntervals(intervals));
    }

    /**
     * 动态规划（有点类似Leetcode300-最长递增子序列）
     *
     * @param intervals
     * @return
     */
    public static int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) {
            return 0;
        }

        Arrays.sort(intervals, (interval1, interval2) -> interval1[0] - interval2[0]); // 升序排序

        int n = intervals.length;
        int[] f = new int[n]; // 数组记录第i个区间元素可以达到的最大不相交区间的个数
        Arrays.fill(f, 1);
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (intervals[j][1] <= intervals[i][0]) {
                    f[i] = Math.max(f[i], f[j] + 1);
                }
            }
        }
        return n - Arrays.stream(f).max().getAsInt();
    }

    /**
     * 贪心算法
     *
     * @param intervals
     * @return
     */
    public int eraseOverlapIntervals2(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));
        int i;
        int j;
        i = 0;
        int count = 1;
        for (j = 1; j < intervals.length; j++) {
            if (intervals[j][0] >= intervals[i][1]) {
                i = j;
                count++;
            }
        }
        return intervals.length - count;
    }
}